class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
            // 将根节点入栈
            stack.push(root);
            while (!stack.isEmpty()) {
            // 取出栈顶元素
            TreeNode tmp = stack.pop();
            if (tmp != null) {
            ans.add(tmp.val);
            // 将其孩子节点压入栈中（先右节点、再左节点）
            stack.add(tmp.right);
            stack.add(tmp.left);
            }
            }
            return ans;
            }

            public List<Integer> inorderTraversal(TreeNode root) {
                List<Integer> ans = new ArrayList<>();
                    Stack<TreeNode> stack = new Stack<>();
                        while (!stack.isEmpty() || root != null) {
                        // 一直放入左儿子（左）
                        while (root != null) {
                        stack.push(root);
                        root = root.left;
                        }
                        // 访问当前元素（根），把右儿子入栈（右）
                        if (!stack.isEmpty()) {
                        root = stack.pop();
                        ans.add(root.val);
                        root = root.right;
                        }
                        }
                        return ans;
                        }


                        public List<Integer> postorderTraversal(TreeNode root) {
                            LinkedList<Integer> ans = new LinkedList<>();
                                if (root == null) {
                                return ans;
                                }

                                Stack<TreeNode> stack = new Stack<>();
                                    stack.push(root);

                                    while (!stack.isEmpty()) {
                                    TreeNode node = stack.pop();
                                    ans.addFirst(node.val);
                                    if (node.left != null) {
                                    stack.push(node.left);
                                    }
                                    if (node.right != null) {
                                    stack.push(node.right);
                                    }
                                    }
                                    return ans;
                                    }
                                    }


